/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue> 
#include <stack>
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>
#include <iterator>
#include<numeric>  // 用于对vector求和----accumulate函数
// #define NDEBUG
#include <assert.h>
using namespace boost;   // 支持string的操作
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

// 遍历
template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit_arr(vector<T>& arr, string const str){
    cout << str << ": ";
    // typename T::const_iterator it = arr.begin();
    for(auto it=arr.begin();it!=arr.end();++it){
        cout << *it <<" ";
    }
    cout<<endl;
}

// 遍历
// template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit2_arr(vector<int>& arr, string const str){
    cout << str << ": ";
    for(int i; i < arr.size(); ++i){
        cout << arr[i] << " ";
    }
    cout<<endl;
}



// 链表结点
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void visit_list(ListNode* head){
    ListNode* tmp = head;
    while(tmp != nullptr){
        cout << tmp->val << ' ';
        tmp = tmp->next;
    }
    cout << endl;
}

// 二叉树--孩子兄弟表示法
//Definition for a binary tree node.// 二叉树--孩子兄弟表示法
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// https://leetcode-cn.com/problems/implement-strstr/
// 注意一个问题 abab 和 abac的next数组是一样的
class Solution {
public:
    // s为文本串，t为模式串. t为空返回0，找到匹配的则返回匹配位置的起始索引，否则返回-1
    int strStr(string s, string t) {
        int lenS = s.length(), lenT = t.length();
        if(lenT == 0) return 0;
        vector<int> next(lenT,0);
        // 获得next数组
        getNext(next,t);

        // 进行模式匹配
        int i=0,j=-1;  // 因为next数组里记录的起始位置为-1
        for (int i=0; i<lenS && j <lenT; i++) {
            while (j >= 0 && s[i] != t[j+1]){  // 不匹配
                j = next[j];  // j 寻找之前匹配的位置
            }
            if (s[i] == t[j+1]) {  // 匹配，j和i同时向后移动
                j++;  // i的增加在for循环里
            }
            if (j == (lenT-1)) { 
                return i - lenT + 1;
            }
        }
        return -1;

    }
    // void getNext(vector<int>& next, string t) {
    //     int i = 0; // 进行遍历模式，开始找前后缀
    //     int j = -1; // 第0个默认是没有最长前后缀的
    //     next[0] = j;  // 初始化

    //     while(i < t.length()) {
    //         // 能进行匹配并且匹配失败时--回溯
    //         if(j >=0 && t[i] != t[j]){
    //             j = next[j];
    //         } else {
    //             // 不能进行匹配或者匹配成功时记录
    //             ++i;
    //             ++j;
    //             next[i] = j;
    //         }
    //     }
    //     visit_arr(next,"自己 nest: ");
    // }
    void getNext(vector<int>& next, string t){
        int j = -1;
        next[0] = j;
        for (int i=1; i<t.length(); i++) {  // 注意i从1开始
            while (j >= 0 && t[i] != t[j+1]) {  // 前后缀不相同了
                j = next[j]; // 回退
            }
            if (t[i] == t[j+1]) { // 找到相同的前后缀
                j++;
            }
            next[i] = j;
        }
        visit_arr(next,"卡尔 nest: ");
    }

};


int main(int argc, const char** argv) {
    Solution solu = Solution();
    // string haystack = "hello", needle = "ll"; // 2
    // string haystack = "mississippi", needle = "issip"; // 4
    // string haystack = "aabaaabaaac", needle = "aabaaac"; // 4
    // string haystack = "aabaaabaaac", needle = "aabaaab"; // 4
    string haystack = "aabaaabaaac", needle = "abcabx"; // 4
    
    time_t start = time(NULL);
    cout << "start time is " << start << endl;

    cout << solu.strStr(haystack, needle) << endl;
    
    time_t end = time(NULL);
    cout << "end time is " << start << endl;
    cout << "耗时：" << end*100-start*100 << " s." <<endl;


    return 0;
}